﻿////////////////////////////////////////////////////////////////////////////////////////////////
//
// Copyright © Yaroslavov Alexander 2010
//
// Contacts:
// Phone: +7(906)827-27-51
// Email: x-ronos@yandex.ru
//
/////////////////////////////////////////////////////////////////////////////////////////////////

using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;

namespace Moppet.Lapa
{
	/// <summary>
	/// Парсеры на лямбда-выражениях. Lp - сокращение от Lambda Parsers.
	/// </summary>
	public static partial class Lp
	{
		/// <summary>
		/// Возвращает все результаты поиска соответствий по всему тексту.
		/// Последовательно применяет parser к тексту, передавая в parser остаток от предыдущего успешного результата, до тех пор,
		/// пока распознаётся текст. Возвращает все найденные соответствия. Между найденными соответствиями не может быть
		/// разрывов.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Блок текста.</param>
		/// <returns>Результаты.</returns>
		public static IEnumerable<LpNode> Matches(LpmParser parser, LpText text)
		{
			foreach (var res in parser.Do(text))
			{
				yield return res;

				// Если предыдущий результат продуктивен и если есть остаток, ищем далее.
				if (res.Match.Length > 0 && res.Rest.Length > 0)
				{
					foreach (var sub in Matches(parser, res.Rest))
						yield return sub;
				}
			}
		}

		/// <summary>
		/// Последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех пор
		/// пока распознаётся текст. Возвращает все найденные соответствия. Между найденными соответствиями не может быть
		/// разрывов.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Блок текста.</param>
		/// <returns>Результаты.</returns>
		public static IEnumerable<LpNode> Matches(LpsParser parser, LpText text)
		{
			return Chain(parser, text);
		}

		#region Tokens

		/// <summary>
		/// Парсер одного символа.
		/// </summary>
		/// <param name="predicate">Лямбда для идентификации символа.</param>
		/// <returns>Парсер символа.</returns>
		public static LpsParser One(Func<char, bool> predicate)
		{
            //TODO: Переделать в LpLex на Expression
            return new LpsParser((p) => p.Length > 0 && predicate(p[0]) ? new LpNode(p, 1) : new LpNode(p));
		}

		/// <summary>
		/// Парсер символа.
		/// </summary>
		/// <param name="ch">Символ.</param>
		/// <returns>Парсер терма.</returns>
		public static LpsParser Char(char ch)
		{
            return new LpsParser((p) => p.Length > 0 && p[0] == ch ? new LpNode(p, 1) : new LpNode(p));
		}

		/// <summary>
		/// Парсер одного числа [0;9].
		/// </summary>
		/// <returns>Парсер терма.</returns>
		public static LpsParser Digit()
		{
            return new LpsParser((p) => p.Length > 0 && char.IsDigit(p[0]) ? new LpNode(p, 1) : new LpNode(p));
		}

        /// <summary>
        /// Парсер одной десятичной цифры в заданном диапазоне [minValue;maxValue].
        /// Например, вы ожидаете цифру только от 1 до 6, тогда вызывайте Lp.Digit(1, 6).
        /// </summary>
        /// <param name="minDigitValue">Минимальное значение  [0;9].</param>
        /// <param name="maxDigitValue">Максимальное значение [0;9].</param>
        /// <returns>Парсер.</returns>
        public static LpsParser Digit(int minDigitValue, int maxDigitValue)
        {
            return new LpsParser((p) =>
            {
                if (p.Length <= 0 || !char.IsDigit(p[0]))
                    return new LpNode(p);
                int value = (p[0] - '0');
                return (minDigitValue >= value && value <= maxDigitValue) ? new LpNode(p, 1) : new LpNode(p);
            });
        }
		
		/// <summary>
		/// Парсер одного литерала.
		/// </summary>
		/// <returns>Парсер терма.</returns>
		public static LpsParser Letter()
		{
            return new LpsParser((text) => text.Length > 0 && char.IsLetter(text[0]) ? new LpNode(text, 1) : new LpNode(text));
		}

		/// <summary>
		/// Парсер одного литерала или цифры.
		/// </summary>
		/// <returns>Парсер терма.</returns>
		public static LpsParser LetterOrDigit()
		{
            return new LpsParser((text) => text.Length > 0 && char.IsLetterOrDigit(text[0]) ? new LpNode(text, 1) : new LpNode(text));
		}


		/// <summary>
		/// Парсер поиска цифр в заданном диапазоне.
		/// </summary>
		/// <param name="minCount">Минимальное допустимое количество цифр, но не менее.</param>
		/// <param name="maxCount">Мaксимальное допустимое количество цифр, но не более.</param>
		/// <returns>Жадный парсер.</returns>
		public static LpsParser Digits(int minCount = 1, int maxCount = int.MaxValue)
		{
            return Range(c => c >= '0' && c <= '9', minCount, maxCount);
		}

        /// <summary>
        /// Парсер поиска цепочки символов в заданном диапазоне.
        /// Жадный алгоритм, т.е. возьмёт максимальную разрешённую последовательность.
        /// </summary>
        /// <param name="predicate">Лямбда поиска.</param>
        /// <param name="minCount">Минимальное допустимое количество символов, но не менее.</param>
        /// <param name="maxCount">Мaксимальное допустимое количество символов, но не более.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser Range(Expression<Func<char, bool>> predicate, int minCount, int maxCount)
        {
            if (minCount < 0)
                throw new ArgumentOutOfRangeException("minCount", "minCount must be greater than or equal zero.");

            if (minCount > maxCount)
                throw new ArgumentOutOfRangeException("maxCount", "maxCount must be greater than or equal minCount.");

            var func = LpLex.Range(predicate, minCount, maxCount).Compile();
            return new LpsParser(func);
        }

        /// <summary>
        /// Парсер поиска заданного количества символов в допустимом диапазоне.
        /// Жадный алгоритм, т.е. возьмёт максимальную разрешённую последовательность.
        /// </summary>
        /// <param name="ch">Символ.</param>
        /// <param name="minCount">Минимальное допустимое количество символов, но не менее.</param>
        /// <param name="maxCount">Мaксимальное допустимое количество символов, но не более.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser Range(char ch, int minCount, int maxCount)
        {
            if (minCount < 0)
                throw new ArgumentOutOfRangeException("minCount", "minCount must be greater than or equal zero.");

            if (minCount > maxCount)
                throw new ArgumentOutOfRangeException("maxCount", "maxCount must be greater than or equal minCount.");

            return new LpsParser((text) =>
            {
                int end = text.Length > maxCount ? (maxCount + 1) : text.Length;
                int cur = 0, ind = text.Index;
                var str = text.Source;
                while (cur < end && str[ind] == ch) { ++ind; ++cur; }
                return (cur >= minCount && cur <= maxCount) ? new LpNode(text, cur) : new LpNode(text);
            });
        }

		/// <summary>
		/// Парсер для поиска одного или более литерала.
		/// </summary>
		/// <returns>Парсер для определения одного или более литерала.</returns>
		public static LpsParser Letters()
		{
			return new LpsParser((text) =>
			{
				int end = text.Length, cur = 0, ind = text.Index;
				var str = text.Source;
				while (cur < end && char.IsLetter(str[ind])) { ++ind; ++cur; }
                return cur > 0 ? new LpNode(text, cur) : new LpNode(text);
			});
		}


		/// <summary>
		/// Жадный парсер поиска одного или более символа.
		/// </summary>
		/// <param name="predicate">Предикат.</param>
		/// <returns>Жадный парсер поиска одного или более символа.</returns>
		public static LpsParser OneOrMore(this Expression<Func<char, bool>> predicate)
		{
            var func = LpLex.OneOrMore(predicate).Compile();
            return new LpsParser(func);
		}

		/// <summary>
		/// Парсер поиска одного или более символа. Жадный алгоритм, зато быстрый.
		/// </summary>
		/// <param name="ch">Символ.</param>
		/// <returns>Парсер поиска одного или более символа.</returns>
		public static LpsParser OneOrMore(char ch)
		{
			return new LpsParser((text) =>
			{
                //fixed (char* end = text.Source + text.Index + text.Length)
                //{
                //    char* beg = end - text.Length, ind = beg;
                //    while (ind < end && *ind == ch) ++ind;

                //    return ind > beg ? new LpNode(text, (int)(ind - beg)) : LpNode.Fail(text);
                //}

                int cur = 0, end = text.Length, ind = text.Index;
                var str = text.Source;
                while (cur < end && str[ind] == ch) { ++ind; ++cur; }
                return cur > 0 ? new LpNode(text, cur) : new LpNode(text);
			});
		}


		/// <summary>
        /// Парсер некоторого идентификатора или имени (терма), которое должно начинаться с определённого набора символов (например только с букв), а
		/// требования к последующим символам другие. Также у имени всегда ограничена длинна.
		/// </summary>
		/// <param name="firstChar">Первый символ.</param>
		/// <param name="maybeNextChars">Ноль и более последующих символов.</param>
        /// <param name="maxLength">Максимальная длина имени.</param>
		/// <returns>Жадный парсер.</returns>
        public static LpsParser Name(Expression<Func<char, bool>> firstChar, Expression<Func<char, bool>> maybeNextChars, int maxLength = int.MaxValue)
		{
            var func = LpLex.Name(firstChar, maybeNextChars, maxLength).Compile();
            return new LpsParser(func);

            //var firstCharFunc = firstChar.Compile();
            //var maybeNextCharsFunc = maybeNextChars.Compile();
            //return new LpsParser("Name", (text) =>
            //{
            //    int end = maxLength < text.Length ? maxLength + 1 : text.Length;
            //    int cur = 0, ind = text.Index;
            //    var str = text.Source;
            //    if (cur < end && firstCharFunc(str[ind])) { ++ind; ++cur; } else { return LpNode.Fail(text); }
            //    while (cur < end && maybeNextCharsFunc(str[ind])) { ++ind; ++cur; }
            //    return cur > maxLength ? LpNode.Fail(text) : LpNode.Take(text, cur);
            //});
		}

        /// <summary>
        /// Парсер некоторого идентификатора или доменного имени, которое должно начинаться с определённого набора символов (например только с букв),
        /// а требования к последующим символам другие. У имени также всегда ограничена длинна.
        /// Здесь имя может быть записано через тире (dashChar), причём тире не может повторятся более одного раза подряд (--), быть в начале или конце имени.
        /// После тире или в конце имени допускаются символы lastChars.
        /// </summary>
        /// <param name="firstChars">Первый символ или символы.</param>
        /// <param name="dashChar">Символ, обозначающий тире.</param>
        /// <param name="lastChars">Допустимые символы после тире или в конце имени.</param>
        /// <param name="maxLength">Максимальная длина имени.</param>
        /// <returns>Жадный парсер.</returns>
        public static LpsParser Name(Expression<Func<char, bool>> firstChars, char dashChar, Expression<Func<char, bool>> lastChars, int maxLength = int.MaxValue)
        {
            var func = LpLex.Name(firstChars, dashChar, lastChars, maxLength).Compile();
            return new LpsParser(func);
        }

		
		/// <summary>
		/// Парсер, который ищет соответствие для заданного терма.
		/// </summary>
		/// <param name="term">Слово, т.е. какая-то последовательность символов.</param>
		/// <returns>Результат.</returns>
		public static LpsParser Term(string term)
		{
            return new LpsParser((text) => text.StartsWith(term) ? new LpNode(text, term.Length) : new LpNode(text));
		}

		/// <summary>
		/// Парсер, который ищет соответствие для любого заданного слова.
		/// Соответствует конструкции регулярного выражения: (a|b|c), где a, b и c - это слова.
		/// Слова сопоставляются в той последовательности, в которой они передаются через аргументы.
		/// Например, если искать "(ab|a)" в строке "ab", то будет найдено "ab", а если
		/// будем искать "(a|ab)", то будет найдена только первая буква.
		/// </summary>
		/// <param name="words">Слова. Пустые слова передавать сюда нельзя.</param>
		/// <returns>Результат для одного из найденных слов. </returns>
		public static LpsParser Any(params string[] words)
		{
            // Внимание!
            // Вариант Any(params char[] chars) через Expression реализовывать не надо,
            // т.к. вот это Lp.One(c => c == '0' || c == '1' ...) всё равно работает быстрее в несколько раз.
            
            // TODO: есть вариант ускорить поиск используя деревья и поиск по хеш-таблице.
            //
			return new LpsParser((text) =>
			{
				int wc = words.Length;
				int tl = text.Length;

				if (tl <= 0)
                    return new LpNode(text);

				for (int i = 0; i < wc; ++i)
				{
					string word = words[i];
					if (text.StartsWith(word))
						return new LpNode(text, word.Length);
				}
                return new LpNode(text);
			});
		}

		#endregion // Tokens

		#region Special


        /// <summary>
        /// Makes new copy of the parser's and sets WrapNode to true.
        /// </summary>
        /// <param name="parser">Parser.</param>
        /// <returns>New parser.</returns>
        public static LpsParser Wrap(this LpsParser parser)
        {
            if (parser.Identifier == null)
                throw new ArgumentException("The 'Identifier' property should be initialized.");
            if (parser.Recurse)
                return Wrap(parser, parser.Identifier);
            return new LpsParser(id: parser.Identifier, wrapNode: true, parser: parser.Parser, recurse: false);
        }

        /// <summary>
        /// Wrap the parser into new parser to wrap the node and mark it by new id.
        /// 
        /// Создаёт пустую обёртку над парсером parser, чтобы результирующий узел 
        /// также обернуть в дополнительный узел и пометить идентификатором.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="id">Новый парсер с новым идентификатором.</param>
        /// <returns>New parser as wrapper.</returns>
        public static LpsParser Wrap(this LpsParser parser, string id)
        {
            if (parser.Identifier == null)
                return new LpsParser(id, wrapNode: true, parser: parser.Recurse ? parser.Do : parser.Parser);
            return new LpsParser(id, wrapNode: true, parser: parser.Do);
        }
        
        /// <summary>
        /// Wrap the parser into new parser to wrap the node and mark it by new id.
        /// 
        /// Создаёт пустую обёртку над парсером parser, чтобы результирующий узел 
        /// также обернуть в дополнительный узел и пометить идентификатором.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="id">Новый парсер с новым идентификатором.</param>
        /// <returns>New parser as wrapper.</returns>
        public static LpsParser Wrap(this LpsChain parser, string id)
        {
            var par = parser.ToParser();
            if (par.Identifier == null)
                return new LpsParser(id, wrapNode: true, parser: par.Recurse ? par.Do : par.Parser);
            return new LpsParser(id, wrapNode: true, parser: par.Do);
        }

		/// <summary>
		/// Конец текстового блока, т.е. возвращает успешное пустое соответствие, если остаток пустой.
		/// </summary>
		/// <returns>Парсер конца текстового блока.</returns>
		public static LpsParser End
		{
            get { return new LpsParser((text) => text.Length == 0 ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text)); }
		}

        /// <summary>
        /// Возвращает успешное пустое соответствие, если дальше есть какой-то текст.
        /// </summary>
        /// <returns>Парсер.</returns>
        public static LpsParser NotEnd
        {
            get { return new LpsParser((text) => text.Length > 0 ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text)); }
        }

		/// <summary>
		/// Парсер пустого успешного соответствия.
		/// Всегда возвращает пустое соответствие.
		/// </summary>
		/// <returns>Парсер.</returns>
		public static LpsParser Empty
		{
            get { return new LpsParser("Empty", (text) => new LpNode(new LpText(text.Source, text.Index, 0), text)); }
		}

        /// <summary>
        /// Парсер, который всегда возвращает неудачу даже не приступая к разбору текста.
        /// Этот парсер хорошо использовать в комбинаторе с условием Lp.If.
        /// </summary>
        /// <returns>Парсер.</returns>
        public static LpsParser Fail
        {
            get { return new LpsParser("Fail", (p) => new LpNode(p)); }
        }

		/// <summary>
		/// Возвращает соответствие максимальной длины или null.
		/// Все соответствия должны принадлежать одному источнику.
		/// </summary>
		/// <param name="results">Список соответствий. Все соответствия должны принадлежать одному источнику.</param>
		/// <returns>Узел или null.</returns>
		public static LpNode Max(this IEnumerable<LpNode> results)
		{
			int maxLen = -int.MaxValue;
			LpNode maxResult = null;

			foreach (var r in results)
			{
				if (r.Rest.Length == 0) // Если нет остатка, значит это максимальная длина.
					return r;

				if (r.Match.Length > maxLen)
				{
					maxLen = r.Match.Length;
					maxResult = r;
				}
			}
			return maxResult;
		}

		/// <summary>
		/// Преобразует мультипарсер, возвращающий множество вариантов разбора, в сингл (парсер с одним результатом), выбирая соответствие максимальной длинны.
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <returns>Синглпарсер.</returns>
		public static LpsParser TakeMax(this LpmParser parser)
		{
            return new LpsParser((p) => parser.Do(p).Max() ?? new LpNode(parser.Identifier, p));
		}

		/// <summary>
		/// Преобразует мультипарсер, возвращающий множество вариантов разбора, в сингл (парсер с одним результатом),
		/// выбирая (ожидая) первое и единственное соответствие.
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <returns>Синглпарсер.</returns>
		public static LpsParser TakeOne(this LpmParser parser)
		{
            return new LpsParser((p) => parser.Do(p).FirstOrDefault() ?? new LpNode(parser.Identifier, p));
		}

		/// <summary>
		/// Добавляет к парсеру фильтр, который отбирает результаты в заданном диапазоне длинн.
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <param name="minLength">Минимальная допустимая длинна соответствия.</param>
		/// <param name="maxLength">Максимальная допустимая длинна соответствия.</param>
		/// <returns>Мультипарсер с фильтром.</returns>
		public static LpmParser TakeRange(this LpmParser parser, int minLength, int maxLength)
		{
			return new LpmParser((p) => parser.Do(p).Where(r => minLength <= r.Match.Length && r.Match.Length <= maxLength));
		}

        /// <summary>
        /// Добавляет к парсеру функцию обработки (корректировки или проверки) соответствия.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="treat">Обработчик любого (успешного или нет) результата (соответствия).</param>
        /// <returns>Парсер с последующей обработкой результата.</returns>
        public static LpsParser Treat(this LpsParser parser, Func<LpNode, LpNode> treat)
        {
            return new LpsParser(parser.Identifier, (t) =>
            {
                var node = parser.Do(t);
                return treat(node);
            });
        }

        /// <summary>
        /// Добавляет к парсеру функцию обработки (корректировки или проверки) соответствия,
        /// если соответствие успешено (Success).
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="treat">Обработчик удачного результата (соответствия).</param>
        /// <returns>Парсер с последующей обработкой результата.</returns>
        public static LpsParser TreatSuccess(this LpsParser parser, Func<LpNode, LpNode> treat)
        {
            return new LpsParser(parser.Identifier, (t) =>
            {
                var node = parser.Do(t);
                if (!node.Success)
                    return node;
                return treat(node);
            });
        }

        /// <summary>
        /// Добавляет к парсеру функцию обработки (корректировки или проверки) соответствия,
        /// если соответствие неудачно (!Success).
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="treat">Обработчик неудачного результата (соответствия).</param>
        /// <returns>Парсер с последующей обработкой результата.</returns>
        public static LpsParser TreatFail(this LpsParser parser, Func<LpNode, LpNode> treat)
        {
            return new LpsParser(parser.Identifier, (t) => 
            {
                var node = parser.Do(t);
                if (node.Success)
                    return node;
                return treat(node);
            });
        }


		/// <summary>
		/// Добавляет к парсеру произвольный фильтр результатов.
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <param name="filter">Фильтр соответствий. Принимает соответствие, возвращает ложь, если это соответствие нужно исключить из результатов.</param>
		/// <returns>Мультипарсер с фильтром.</returns>
		public static LpmParser Filter(this LpmParser parser, Func<LpText, bool> filter)
		{
			return new LpmParser((p) => parser.Do(p).Where(r => filter(r.Match)));
		}

		/// <summary>
        /// Парсер, который анализирует символ, находящийся перед блоком текста (Lookbehind).
		/// Т.е. он заглядывает на символ назад, если блок текста не сначала строки.
        /// Если символ удовлетворяет условию behindChar или если это начало строки, возвращает пустое успешное соответствие,
		/// в противном случае возвращает неудачу.
		/// </summary>
		/// <param name="behindChar">Ф-я идентификации нужного нам символа.</param>
		/// <returns>Успешное пустое соответствие или неудачное.</returns>
		public static LpsParser Lookbehind(Func<char, bool> behindChar)
		{
            return new LpsParser((text) => text.Index <= 0 || behindChar(text[-1]) ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text));
		}

        /// <summary>
        /// Парсер, который анализирует символ, находящийся перед блоком текста (lookahead).
        /// Т.е. он заглядывает на символ назад, если блок текста не сначала строки.
        /// Если символ равен behindChar или если это начало строки, возвращает пустое успешное соответствие,
        /// в противном случае возвращает неудачу.
        /// </summary>
        /// <param name="behindChar">Нужный нам символ.</param>
        /// <returns>Успешное пустое соответствие или неудачное.</returns>
        public static LpsParser Lookbehind(char behindChar)
        {
            return new LpsParser((text) => text.Index <= 0 || behindChar == text[-1] ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text));
        }

        /// <summary>
        /// Парсер, который анализирует следующий символ но не захватывает его, т.е. возвращает пустое успешное соответствие
        /// если символ удовлетворяет условию или если мы в конце текста, в противном случае возвращает неудачу.
        /// </summary>
        /// <param name="aheadChar">Ф-я идентификации нужного нам символа.</param>
        /// <returns>Успешное пустое соответствие или неудачное.</returns>
        public static LpsParser Lookahead(Func<char, bool> aheadChar)
        {
            return new LpsParser((text) => (text.Length <= 0 || aheadChar(text[0]) ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text)));
        }

        /// <summary>
        /// Парсер, который анализирует следующий символ но не захватывает его, т.е. возвращает пустое успешное соответствие
        /// если символ удовлетворяет условию или если мы в конце текста, в противном случае возвращает неудачу.
        /// </summary>
        /// <param name="aheadChar">Ф-я идентификации нужного нам символа.</param>
        /// <returns>Успешное пустое соответствие или неудачное.</returns>
        public static LpsParser Lookahead(char aheadChar)
        {
            return new LpsParser((text) => (text.Length <= 0 || text[0] == aheadChar ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text)));
        }

        /// <summary>
        /// Применяет парсер и проверяет результат на истинность, но не захватывает его, т.е. возвращает пустое успешное соответствие,
        /// если парсер успешно выполнился или если мы в конце текста, в противном случае возвращает неудачу.
        /// </summary>
        /// <param name="ahead">Парсер, который проверяет, а что же там дальше есть?</param>
        /// <returns>Успешное пустое соответствие или неудачное.</returns>
        public static LpsParser Lookahead(LpsParser ahead)
        {
            return new LpsParser((text) => (text.Length <= 0 || ahead.Do(text).Success ? new LpNode(new LpText(text.Source, text.Index, 0), text) : new LpNode(text)));
        }


        /// <summary>
        /// Модифицирует парсер, добавляя к нему проверку ahead и behind.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="behind">Проверка символа назад.</param>
        /// <param name="ahead">Проверка символа вперёд.</param>
        /// <returns>Модифицированный парсер.</returns>
        public static LpsParser Look(this LpsParser parser, Func<char, bool> behind = null, Func<char, bool> ahead = null)
        {
            if (ahead != null && behind != null) return new LpsParser(id: parser.Identifier, wrapNode: parser.WrapNode, recurse: parser.Recurse, parser: (t) =>
            {
                if (!(t.Index <= 0 || behind(t[-1])))
                    return new LpNode(t);
                var res = parser.Parser(t);
                if (res.Match.Length < 0)
                    return res;
                return (res.Rest.Length <= 0 || ahead(res.Rest[0])) ? res : new LpNode(t);
            });

            if (behind != null) return new LpsParser(id: parser.Identifier, wrapNode: parser.WrapNode, recurse: parser.Recurse, parser: (t) =>
            {
                if (!(t.Index <= 0 || behind(t[-1])))
                    return new LpNode(t);
                return parser.Parser(t);
            });

            if (ahead != null) return new LpsParser(id: parser.Identifier, wrapNode: parser.WrapNode, recurse: parser.Recurse, parser: (t) =>
            {
                var res = parser.Parser(t);
                if (res.Match.Length < 0)
                    return res;
                return (res.Rest.Length <= 0 || ahead(res.Rest[0])) ? res : new LpNode(t);
            });

            throw new ArgumentNullException("behind");
        }

		/// <summary>
		/// Парсер с условием. Позволяет выбрать стратегию разбора, предварительно проверив условие.
		/// </summary>
		/// <param name="condition">Условие.</param>
		/// <param name="ifTrue">Если условие истинно.</param>
		/// <param name="ifFalse">Если условие ложно.</param>
		/// <returns>Парсер с условием.</returns>
		public static LpsParser If(char condition, LpsParser ifTrue, LpsParser ifFalse)
		{
			return new LpsParser((t) =>
			{
				if (t.Length <= 0)
                    return new LpNode(t);
				return t[0] == condition ? ifTrue.Do(t) : ifFalse.Do(t);
			});
		}

		/// <summary>
		/// Парсер с условием. Позволяет выбрать стратегию разбора, предварительно проверив условие.
		/// </summary>
		/// <param name="condition">Условие.</param>
		/// <param name="ifTrue">Если условие истинно.</param>
		/// <param name="ifFalse">Если условие ложно.</param>
		/// <returns>Парсер с условием.</returns>
		public static LpsParser If(Func<char, bool> condition, LpsParser ifTrue, LpsParser ifFalse)
		{
			return new LpsParser((t) =>
			{
				if (t.Length <= 0)
                    return new LpNode(t);
				return condition(t[0]) ? ifTrue.Do(t) : ifFalse.Do(t);
			});
		}

        /// <summary>
        /// Парсер с условием. Позволяет выбрать стратегию разбора, предварительно проверив условие.
        /// </summary>
        /// <param name="condition">Условие.</param>
        /// <param name="ifTrue">Если условие истинно.</param>
        /// <param name="ifFalse">Если условие ложно.</param>
        /// <returns>Парсер с условием.</returns>
        public static LpsParser If(LpsParser condition, LpsParser ifTrue, LpsParser ifFalse)
        {
            return new LpsParser((t) => condition.Do(t).Success ? ifTrue.Do(t) : ifFalse.Do(t));
        }

    	/// <summary>
		/// Возвращает специфический парсер одного символа.
		/// Этот парсер выбирает символ, если он не является начальным для некоторой цепочки, которую распознаёт parser.
		/// Lp.Not(Lp.Term("345")).OneOrMore().Do("12345") == "12".
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Парсер одного символа.</returns>
		public static LpsParser Not(this LpsParser parser)
		{
			string id = null;
			if (!string.IsNullOrWhiteSpace(parser.Identifier))
				id = "Not(" + parser.Identifier + ")";

			return new LpsParser((text) =>
			{
                if (text.Length <= 0)
                    return new LpNode(id, text);
				var result = parser.Do(text);
                return result.Success ? new LpNode(id, text) : new LpNode(text, 1, id);
			});
		}

		/// <summary>
		/// Возвращает успешное соответствие минимальной длинны, которое удалось распознать парсеру, начиная от некоторого индекса и до конца текстового блока. 
		/// Пример: new LpText("12345").EndsWith(Lp.Digits()).Match == "5";
		/// </summary>
		/// <param name="text">Текстовый блок (строка).</param>
		/// <param name="parser">Парсер.</param>
		/// <returns>Успешное соответствие без остатка или неудачное соответствие.</returns>
		public static LpNode EndsWith(this LpText text, LpsParser parser)
		{
			int initialLength = text.Length;
			int currentLength = 0;
			
			while (++currentLength <= initialLength)
			{
				var res = parser.Do(new LpText(text.Source, text.Index + initialLength - currentLength, currentLength));
				if (res.Success)
					return res;
			}
            return new LpNode(text);
		}

        /// <summary>
        /// Меморизация. Обычно редко помогает ускорить парсинг простых конструкций, но инногда она, всё таки, его ускоряет существенно.
        /// Вот типичный парсер: (a|a+b|a+b+c|a+b+c+d), где a - часть, которая будет три раза повторно вычисляться и поэтому подходит для меморизации.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <param name="storage">Хранилище результатов.</param>
        /// <param name="sync">Синхронизация доступа к словарю. Объект синхронизаци - сам словарь.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser Mem(this LpsChain parser, IDictionary<LpText, LpMemNode> storage = null, bool sync = true)
        {
            return Mem(parser.ToParser(), storage);
        }

		/// <summary>
		/// Меморизация. Обычно редко помогает ускорить парсинг простых конструкций, но инногда она, всё таки, его ускоряет существенно.
		/// Вот типичный парсер: (a|a+b|a+b+c|a+b+c+d), где a - часть, которая будет три раза повторно вычисляться и поэтому подходит для меморизации.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="storage">Хранилище результатов.</param>
        /// <param name="sync">Синхронизация доступа к словарю. Объект синхронизаци - сам словарь.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser Mem(this LpsParser parser, IDictionary<LpText, LpMemNode> storage = null, bool sync = true)
		{
			return new LpsParser(id: null, wrapNode: false, parser: Mem(parser.Do, storage));
		}


		/// <summary>
		/// Меморизация.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="storage">Хранилище результатов.</param>
        /// <param name="sync">Синхронизация доступа к словарю. Объект синхронизаци - сам словарь.</param>
		/// <returns>Парсер.</returns>
		public static Func<LpText, LpNode> Mem(this Func<LpText, LpNode> parser, IDictionary<LpText, LpMemNode> storage, bool sync = true)
		{
			if (storage == null)
                storage = new Dictionary<LpText, LpMemNode>(0x31);

            if (sync)
            {
                return (t) =>
                {
                    LpMemNode memRes = null;
                    lock (storage)
                    {
                        if (storage.TryGetValue(t, out memRes))
                        {
                            ++memRes.Count;
                            return memRes.Node;
                        }
                    }
                    var prevNodes = -1;
                    lock (storage)
                    {
                        prevNodes = storage.Count;
                    }
                    var resultNode = parser(t);

                    lock (storage)
                    {
                        if (prevNodes == storage.Count)   // Если Count не поменялся, значит словарь ни кто не трогал и ContainsKey повторно можно не проверять.
                            storage.Add(t, new LpMemNode(resultNode));
                        else if (!storage.ContainsKey(t)) // Двойная проверка из-за возможной рекурсии.
                            storage.Add(t, new LpMemNode(resultNode));
                    }
                    return resultNode;
                };
            }
			return (t) =>
			{
                LpMemNode memRes = null;
                if (storage.TryGetValue(t, out memRes))
                {
                    ++memRes.Count;
                    return memRes.Node;
                }

                var prevNodes = storage.Count;
				var resultNode = parser(t);

                if (prevNodes == storage.Count)   // Если Count не поменялся, значит словарь ни кто не трогал и ContainsKey повторно можно не проверять.
                    storage.Add(t, new LpMemNode(resultNode));
                else if (!storage.ContainsKey(t)) // Двойная проверка из-за возможной рекурсии.
                    storage.Add(t, new LpMemNode(resultNode));
                return resultNode;
			};
		}

		/// <summary>
		/// Строит парсер для разбора некоторого выражения в скобках с учётом любой вложенности, т.е. (((body))).
		/// </summary>
		/// <param name="openBracket">Открывающая скобка.</param>
		/// <param name="body">Тело.</param>
		/// <param name="closeBracket">Закрывающая скобка.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser InBrackets(LpsParser openBracket, LpsParser body, LpsParser closeBracket)
		{
			return new LpsParser((new LpBrackets(openBracket, body, closeBracket)).Do);
		}

		/// <summary>
		/// Парсер для разбора списка одного или более элементов, записанных, например, через запятую или какой-либо другой разделитель.
		/// Например, числа: 1,2,3.
		/// </summary>
		/// <param name="listItem">Элемент списка.</param>
		/// <param name="delimiter">Разделитель.</param>
		/// <returns>Жадный парсер.</returns>
        public static LpsParser List(LpsParser listItem, char delimiter)
		{
			return new LpsParser((text) =>
			{
				var last = listItem.Do(text);
				if (!last.Success)
					return last;

                var children = new List<LpNode>(0x10);
				children.Add(last);

				while (last.Success)
				{
					var rest = last.Rest;
					if (!(rest.Length > 0 && rest[0] == delimiter))
						break;
					LpNode delim = new LpNode(rest, 1);
					LpNode next = listItem.Do(delim.Rest);
					if (!next.Success)
						break;
					last = next;
					children.Add(delim);
					children.Add(last);
				}
                //TODO: Убирать из children лишнее и пустое, проверить ,,,
				return new LpNode(text, last.Rest.Index - text.Index, "List", children);
			});
		}
		
		/// <summary>
		/// Парсер для разбора списка одного или более элементов, записанных, например, через запятую или какой-либо другой разделитель.
		/// Например, числа: 1,2,3.
		/// Внимание: для параметров maybeSpaces и maybeTail не нужно делать Maybe() самим, это учитывается автоматически.
		/// </summary>
		/// <param name="listItem">Элемент списка.</param>
		/// <param name="delimiter">Разделитель.</param>
		/// <param name="maybeSpaces">Возможные пробелы между разделителем и элементом списка, например Lp.OneOrMore(' '). По умолчанию пробелы не допускаются.</param>
		/// <returns>Жадный парсер.</returns>
		public static LpsParser List(LpsParser listItem, LpsParser delimiter, LpsParser maybeSpaces = null)
		{
			if (maybeSpaces == null) return new LpsParser((text) =>
			{
				var last = listItem.Do(text);
				if (!last.Success)
					return last;

                var children = new List<LpNode>(0x10);
				children.Add(last);

				while (last.Success)
				{
					LpNode delim = delimiter.Do(last.Rest);
					if (!delim.Success)
						break;
					LpNode next = listItem.Do(delim.Rest);
					if (!next.Success)
						break;
					last = next;
					children.Add(delim);
					children.Add(last);
				}
                //TODO: Убирать из children лишнее и пустое, проверить ,,,
                return new LpNode(text, last.Rest.Index - text.Index, "List", children);
			});

			// ------------------------------------------------------------------
			return new LpsParser((text) =>
			{
				var last = listItem.Do(text);
				if (!last.Success)
					return last;

                var children = new List<LpNode>(0x10);
				children.Add(last);

				while(last.Success)
				{
					LpNode s_left = maybeSpaces.Do(last.Rest);
					LpNode delim  = delimiter.Do(s_left.Rest);
					if (!delim.Success)
						break;
					LpNode s_right = maybeSpaces.Do(delim.Rest);
					var next = listItem.Do(s_right.Rest);
					if (!next.Success)
						break;

					// Добавляем пробелы, разделитель и элемент списка.
					last = next;
					if (s_left.Success && s_left.Match.Length > 0)
						children.Add(s_left);
					children.Add(delim);
					if (s_right.Success && s_right.Match.Length > 0)
						children.Add(s_right);
					children.Add(last);
				}
                //TODO: Убирать из children лишнее и пустое, проверить ,,,
				return new LpNode(text, last.Rest.Index - text.Index, "List", children);
			});
		}


        /// <summary>
        /// Эта функция модифицирует парсер body, заимствуя у него все свойства и дочерние узлы, к дочерним узлам ещё добавляет
		/// возможные хвосты слева и справа.
		/// </summary>
		/// <param name="body">Основное тело.</param>
		/// <param name="maybeLeft">Возможный хвост слева, например Lp.Char('{').</param>
		/// <param name="maybeRight">Возможный хвост справа, например Lp.Char('}').</param>
		/// <returns>Жадный парсер.</returns>
        public static LpsParser MaybeTails(this LpsChain body, LpsParser maybeLeft, LpsParser maybeRight)
        {
            return body.ToParser().MaybeTails(maybeLeft, maybeRight);
        }

		/// <summary>
		/// Эта функция модифицирует парсер body, заимствуя у него все свойства и дочерние узлы, к дочерним узлам ещё добавляет
		/// возможные хвосты слева и справа.
		/// </summary>
		/// <param name="body">Основное тело.</param>
		/// <param name="maybeLeft">Возможный хвост слева, например Lp.Char('{').</param>
		/// <param name="maybeRight">Возможный хвост справа, например Lp.Char('}').</param>
		/// <returns>Жадный парсер.</returns>
		public static LpsParser MaybeTails(this LpsParser body, LpsParser maybeLeft, LpsParser maybeRight)
		{
			return new LpsParser(id: body.Identifier, wrapNode: body.WrapNode, recurse: body.Recurse, parser: (text) =>
			{
                var children = new List<LpNode>(0x10);

				LpNode center = null;
				LpNode last = maybeLeft.Do(text);
				if (last.Match.Length > 0)
				{
					children.Add(last);
					center = body.Parser(last.Rest);
				}
				else
				{
                    center = body.Parser(text);
				}
				if (center.Match.Length < 0)
					return center;

				// Добавим дочерние узлы центра.
                children.AddChildrenOrNodeOrNothing(center);

				last = maybeRight.Do(center.Rest);
				if (last.Match.Length > 0)
					children.Add(last);
				else
					last = center;

                return new LpNode(text, last.Rest.Index - text.Index, center.Id, children);
			});
		}

		/// <summary>
		/// Парсер для разбора цепочки бинарных операторов и операндов. Например, 1+2-3/9.
		/// Минимальная конструкция для разбора: a+b, т.е. правый операнд требуется.
		/// </summary>
		/// <param name="leftOperand">Левый или первый операнд.</param>
		/// <param name="binOperator">Бинарный оператор.</param>
		/// <param name="rightOperand">Правый и/или последующие операнды.</param>
		/// <param name="spacesBetween">Парсер пробелов между операндом и оператором, например Lp.ZeroOrMore(' '). По умолчанию пропускает пробелы, табуляцию и переходы на след. строку.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser BinaryExpression(LpsParser leftOperand, LpsParser binOperator, LpsParser rightOperand, LpsParser spacesBetween = null)
		{
			if (spacesBetween == null)
				spacesBetween = Lp.ZeroOrMore(c => c == ' ' || c == '\t' || c == '\r' || c == '\n');

			return new LpsParser((text) =>
			{

                var children = new List<LpNode>(0x10);
				var left = leftOperand.Do(text); // Первый или левый операнд.
				if (left.Match.Length < 0)
					return left;
				children.Add(left);

				var lSpaces = spacesBetween.Do(left.Rest); // Пробелы слева
				if (lSpaces.Match.Length > 0)
					children.Add(lSpaces);
                else if (lSpaces.Match.Length < 0)
                    return lSpaces;

				var oper = binOperator.Do(lSpaces.Rest); // Оператор
				if (oper.Match.Length < 0)
					return oper;
				children.Add(oper);

                var rSpaces = spacesBetween.Do(oper.Rest); // Пробелы справа
                if (rSpaces.Match.Length > 0)
                    children.Add(rSpaces);
                else if (rSpaces.Match.Length < 0)
                    return rSpaces;

                var right = rightOperand.Do(rSpaces.Rest); // Правый операнд.
				if (right.Match.Length < 0)
					return right;
				
				// Далее повторяющийся хвост (оператор-операнд).
				var last = right;
				while (true)
				{
					children.Add(last);
                    lSpaces = spacesBetween.Do(last.Rest); // Пробелы слева
                    if (lSpaces.Match.Length < 0)
                        break;

					var nextOper = binOperator.Do(lSpaces.Rest);
					if (nextOper.Match.Length < 0)
						break;

					rSpaces = spacesBetween.Do(nextOper.Rest);
                    if (rSpaces.Match.Length < 0)
                        break;

                    var nextRight = rightOperand.Do(rSpaces.Rest);
					if (nextRight.Match.Length < 0)
						break;

                    if (lSpaces.Match.Length > 0)
                        children.Add(lSpaces);
                    children.Add(nextOper);
                    if (rSpaces.Match.Length > 0)
                        children.Add(rSpaces);

					last = nextRight;
				}
                return new LpNode(text, last.Rest.Index - text.Index, null, children);
			});
		}

		#endregion Special

		#region Lpm special functions

		/// <summary>
		/// Возвращает множество результатов конкатенации prevResults с результатом разбора nextParser.
		/// </summary>
		/// <param name="prevResults">Варианты разбора на предыдущем шаге.</param>
		/// <param name="nextParser">Варианты разбора на следующем шаге.</param>
		/// <returns>Конкатенация результатов.</returns>
		internal static IEnumerable<LpNode> Next(this IEnumerable<LpNode> prevResults, LpmParser nextParser)
		{
			foreach (var l in prevResults)
				foreach (var r in nextParser.Do(l.Rest))
					yield return LpNode.Concat(l, r);
		}

		/// <summary>
		/// Возвращает множество результатов конкатенации prevResults с результатом разбора nextParser.
		/// В отличие от Next, эта функция фильтрует пустые результаты чтобы предотвратить зацикливание квантификатора, ибо
		/// нельзя соединять пустое чтобы продвинуться вперёд.
		/// </summary>
		/// <param name="prevResults">Варианты разбора на предыдущем шаге.</param>
		/// <param name="nextParser">Варианты разбора на следующем шаге.</param>
		/// <returns>Конкатенация результатов.</returns>
		internal static IEnumerable<LpNode> NextSelf(this IEnumerable<LpNode> prevResults, LpmParser nextParser)
		{
			foreach (var left in prevResults)
			{
				// Если left.Match пустой, то далее продвинуться с помощью того же парсера мы не можем.
				// Если нет остатка left.Rest, то далее вообще продвигаться нет смысла, ибо всё уже проанализировано.
				if (left.Match.Length <= 0 || left.Rest.Length <= 0)
					continue;

				foreach (var right in nextParser.Do(left.Rest))
				{
					if (right.Match.Length > 0)
						yield return LpNode.Concat(left, right);
				}
			}
		}

		/// <summary>
		/// Реализация Distinct для поля Match, т.е. узлы считаются одинаковыми, если поле Match одного узла совпадает с аналогичным полем другого узла.
		/// Прочие поля в сравнении не участвуют.
		/// </summary>
		/// <param name="variants">Варианты разбора текста.</param>
		/// <returns>Очищенная от дублей последовательность.</returns>
		public static IEnumerable<LpNode> DistinctMatches(this IEnumerable<LpNode> variants)
		{
			// TODO: Возможно есть более быстрый способ убирания повторов. Как будет время, обязательно проанализировать.
			return variants.Distinct(new LpNodeMatchComparer());
		}

		/// <summary>
		/// Реализация IEqualityComparer для LpNode. Сравнивается только поле Match.
		/// </summary>
		private class LpNodeMatchComparer : IEqualityComparer<LpNode>
		{
			bool IEqualityComparer<LpNode>.Equals(LpNode x, LpNode y)
			{
				return x.Match.Equals(y.Match);
			}
			int IEqualityComparer<LpNode>.GetHashCode(LpNode obj)
			{
				return obj.Match.GetHashCode();
			}
		}

		/// <summary>
		/// Убирает повторы пустых соответствий из списка вариантов разбора.
		/// Эта функция работает быстро.
		/// </summary>
		/// <param name="variants">Варианты разбора текста.</param>
		/// <returns>Очищенная от дублей последовательность.</returns>
		public static IEnumerable<LpNode> DistinctVoids(this IEnumerable<LpNode> variants)
		{
			bool first = true;
			foreach (var v in variants)
			{
				if (v.Match.Length == 0)
				{
					if (first)
					{
						first = false;
						yield return v;
					}
				}
				else
				{
					yield return v;
				}
			}
		}

		#endregion Lpm special functions

		#region OneOrMore

		internal static IEnumerable<LpNode> OneOrMore_(this LpsParser parser, LpText text)
		{
			var left = parser.Do(text);
			while (left.Success)
			{
				yield return left;

				// Защита от зацикливания.
				// Для Lpm такая проверка есть в функции NextSelf.
				if (left.Match.Length <= 0 || left.Rest.Length <= 0)
					break;

				var right = parser.Do(left.Rest);
				if (!right.Success)
					break;
				left = LpNode.Concat(left, right);
			}
		}

		internal static IEnumerable<LpNode> OneOrMore_(this LpmParser parser, LpText text)
		{
			var results = parser.Do(text);
			while (true)
			{
				// Повторы убирать необходимо обязательно ибо время разбора при неблагоприятных исходах может вырасти экспоненциально.
				results = results.DistinctMatches();
				
				bool empty = true;
				foreach (var oneResult in results)
				{
					empty = false;
					yield return oneResult;
				}
				if (empty)
					yield break;

				results = results.NextSelf(parser);
			}
		}

		/// <summary>
		/// Квантификатор. Один или более раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Мультипарсер.</returns>
		public static LpmParser OneOrMore_(this LpsParser parser)
		{
			return new LpmParser((p) => OneOrMore_(parser, p));
		}

        /// <summary>
        /// Квантификатор. Один или более раз.
        /// </summary>
        /// <param name="predicate">Предикат - функция принадлежности символа заданному множеству.</param>
        /// <returns>Мультипарсер.</returns>
        public static LpmParser OneOrMore_(this Func<char, bool> predicate)
        {
            return OneOrMore_(Lp.One(predicate));
        }

		/// <summary>
		/// Квантификатор. Один или более раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Мультипарсер.</returns>
		public static LpmParser OneOrMore_(this LpmParser parser)
		{
			return new LpmParser((p) => OneOrMore_(parser, p).DistinctMatches());
		}

		/// <summary>
		/// Последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех пор
		/// пока распознаётся текст. Возвращает все найденные соответствия. Между найденными соответствиями не может быть
		/// разрывов.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Блок текста.</param>
		/// <returns>Результаты поиска.</returns>
		internal static IEnumerable<LpNode> Chain(this LpsParser parser, LpText text)
		{
			var res = parser.Do(text);
			while (res.Success)
			{
				yield return res;
				if (res.Match.Length == 0 || res.Rest.Length <= 0)
					break;
				res = parser.Do(res.Rest);
			}
		}


        
        /// <summary>
        /// Конструктор парсера цепочки из одного или более элементов.
		/// Возвращает парсер, который последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех
		/// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
		/// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
		/// </summary>
        /// <param name="parser">Парсер.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser OneOrMore(this LpsChain parser)
        {
            return Lp.OneOrMore((LpCover<LpsParser, LpNode>)parser.ToParser());
        }

        /// <summary>
        /// Конструктор парсера цепочки из одного или более элементов.
        /// Возвращает парсер, который последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех
        /// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
        /// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser OneOrMore(this LpsParser parser)
        {
            return Lp.OneOrMore((LpCover<LpsParser, LpNode>)parser);
        }

		/// <summary>
        /// Конструктор парсера цепочки из одного или более элементов.
		/// Возвращает парсер, который последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех
		/// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
		/// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
		/// </summary>
        /// <param name="parserInfo">Парсер.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser OneOrMore(this LpCover<LpsParser, LpNode> parserInfo)
		{
            var parser = parserInfo.Parser;
            if (!parserInfo.Uncover) return new LpsParser(id: null, wrapNode: true, parser: (text) =>
			{
                var next = parser.Do(text);
				if (!next.Success)
					return next;

                // Оказалось, что List в 1.5 раза работает быстрее чем LinkedList, даже на 10-и миллионных массивах.
                // Да и памяти жрёт на одну треть меньше, если LpNode - класс, а не структура.
                var list = new List<LpNode>(0x10);
				while (next.Match.Length > 0)
				{
					list.Add(next);
					next = parser.Do(next.Rest);
				}
				if (list.Count <= 1)
					return list.Count == 0 ? next : list[0];
				return new LpNode(text, next.Rest.Index - text.Index, null, list);
			});

            return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = parser.Do(text);
                if (!next.Success)
                    return next;

                var list = new List<LpNode>(0x10);
                while (next.Match.Length > 0)
                {
                    list.AddChildrenOrNodeOrNothing(next);
                    next = parser.Do(next.Rest);
                }
                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });
		}

		#endregion

		#region Maybe

		/// <summary>
		/// Более быстрый аналог комбинации parser.Maybe().TakeMax().
		/// </summary>
		/// <param name="parser">Однорезультатный парсер.</param>
		/// <returns>Однорезультатный парсер.</returns>
		public static LpsParser Maybe(this LpsParser parser)
		{
			return new LpsParser((text) =>
			{
				var res = parser.Do(text);
                return res.Success ? res : new LpNode(new LpText(text.Source, text.Index, 0), text);
			});
		}

		/// <summary>
		/// Чуть более быстрый аналог комбинации parser.Maybe().TakeMax().
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <returns>Однорезультатный парсер.</returns>
		public static LpsParser TakeMaxOrEmpty(this LpmParser parser)
		{
			return new LpsParser((text) =>
			{
				var res = parser.Do(text);
				var node = Max(res);
                return node != null ? node : new LpNode(new LpText(text.Source, text.Index, 0), text);
			});
		}

		/// <summary>
		/// Комбинатор. Ноль или один раз.
		/// </summary>
		/// <param name="charPredicat">Парсер одного символа - предикат.</param>
		/// <param name="text">Текст.</param>
		/// <returns>Все варианты соответствий.</returns>
		internal static IEnumerable<LpNode> Maybe_(Func<char, bool> charPredicat, LpText text)
		{
            yield return new LpNode(new LpText(text.Source, text.Index, 0), text);
			if (text.Length > 0 && charPredicat(text[0]))
                yield return new LpNode(text, 1);
		}

		/// <summary>
		/// Комбинатор. Ноль или один раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Текст.</param>
		/// <returns>Все варианты соответствий.</returns>
		internal static IEnumerable<LpNode> Maybe_(LpsParser parser, LpText text)
		{
            yield return new LpNode(new LpText(text.Source, text.Index, 0), text);
			var res = parser.Do(text);
			if (res.Success)
				yield return res;
		}

		/// <summary>
		/// Комбинатор. Ноль или один раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Все варианты соответствий.</returns>
		public static LpmParser Maybe_(this LpsParser parser)
		{
			return new LpmParser((p) => Maybe_(parser, p));
		}

		/// <summary>
		/// Комбинатор. Ноль или один раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Все варианты соответствий.</returns>
		public static LpmParser Maybe_(this LpmParser parser)
		{
			return new LpmParser((p) => Maybe(parser, p));
		}


		/// <summary>
		/// Комбинатор. Ноль или один раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Текст.</param>
		/// <returns>Все варианты соответствий.</returns>
		public static IEnumerable<LpNode> Maybe(this LpmParser parser, LpText text)
		{
            yield return new LpNode(new LpText(text.Source, text.Index, 0), text);
			foreach (var v in parser.Do(text))
				yield return v;
		}

		/// <summary>
		/// Парсер одного символа, если он есть.
		/// </summary>
		/// <param name="ch">Символ.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser Maybe(char ch)
		{
            return new LpsParser((t) => t.Length > 0 && t[0] == ch ? new LpNode(t, 1) : new LpNode(new LpText(t.Source, t.Index, 0), t));
		}

        /// <summary>
        /// Парсер одного символа, если он есть.
        /// </summary>
        /// <param name="ch">Функция идентификации символа.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser Maybe(this Func<char, bool> ch)
        {
            return new LpsParser((t) => t.Length > 0 && ch(t[0]) ? new LpNode(t, 1) : new LpNode(new LpText(t.Source, t.Index, 0), t));
        }


		/// <summary>
		/// Парсер символа с двумя исходами (пусто, символ).
		/// </summary>
		/// <param name="ch">Символ.</param>
		/// <returns>Мультипарсер.</returns>
		public static LpmParser Maybe_(char ch)
		{
			return new LpmParser((p) => Maybe_(c => c == ch, p));
		}


		/// <summary>
		/// Парсер терма, который может быть, а может и не быть.
		/// </summary>
		/// <param name="term">Некоторое слово.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser Maybe(string term)
		{
            return new LpsParser((text) => text.StartsWith(term) ? new LpNode(text, term.Length) : new LpNode(new LpText(text.Source, text.Index, 0), text));
		}

		#endregion // ZeroOrOne

		#region ZeroOrMore

        /// <summary>
        /// Разновидность комбинатора парсеров в цепочку, который отличается от Lp.OneOrMore(LpsParser) тем, что за разбор первого элемента отвечает
        /// firstItemParser, а за разбор последующих элементов отвечает maybeNextItemsParser.
        /// Все найденные соответствия сохраняются в свойстве Children узла.
        /// </summary>
        /// <param name="firstItem">Парсер первого элемента.</param>
        /// <param name="maybeNextItems">Парсер последующих элементов.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser NextZeroOrMore(this LpsChain firstItem, LpsChain maybeNextItems)
        {
            return firstItem.ToParser().NextZeroOrMore(maybeNextItems.ToParser());
        }

        /// <summary>
		/// Разновидность комбинатора парсеров в цепочку, который отличается от Lp.OneOrMore(LpsParser) тем, что за разбор первого элемента отвечает
		/// firstItemParser, а за разбор последующих элементов отвечает maybeNextItemsParser.
		/// Все найденные соответствия сохраняются в свойстве Children узла.
		/// </summary>
		/// <param name="firstItem">Парсер первого элемента.</param>
		/// <param name="maybeNextItems">Парсер последующих элементов.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser NextZeroOrMore(this LpsChain firstItem, LpUncover<LpsParser, LpNode> maybeNextItems)
        {
            return firstItem.ToParser().NextZeroOrMore(maybeNextItems);
        }
		
        /// <summary>
		/// Разновидность комбинатора парсеров в цепочку, который отличается от Lp.OneOrMore(LpsParser) тем, что за разбор первого элемента отвечает
		/// firstItemParser, а за разбор последующих элементов отвечает maybeNextItemsParser.
		/// Все найденные соответствия сохраняются в свойстве Children узла.
		/// </summary>
		/// <param name="firstItem">Парсер первого элемента.</param>
		/// <param name="maybeNextItems">Парсер последующих элементов.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser NextZeroOrMore(this LpsParser firstItem, LpUncover<LpsParser, LpNode> maybeNextItems)
        {
            return NextZeroOrMore((LpUncover<LpsParser, LpNode>)firstItem, maybeNextItems);
        }

		/// <summary>
        /// Реализует шаблон (firstItem + maybeNextItems*).
		/// Разновидность комбинатора парсеров в цепочку, который отличается от Lp.OneOrMore(LpsParser) тем, что за разбор первого элемента отвечает
		/// firstItemParser, а за разбор последующих элементов отвечает maybeNextItemsParser.
		/// Все найденные соответствия сохраняются в свойстве Children узла.
		/// </summary>
		/// <param name="firstItem">Парсер первого элемента.</param>
		/// <param name="maybeNextItems">Парсер последующих элементов.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser NextZeroOrMore(this LpUncover<LpsParser, LpNode> firstItem, LpUncover<LpsParser, LpNode> maybeNextItems)
		{

            if (!maybeNextItems.Uncover) return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = firstItem.Parser.Do(text);
                if (!next.Success)
                    return next;

                var list = new List<LpNode>(0x10);
                if (firstItem.Uncover)
                    list.AddChildrenOrNodeOrNothing(next);
                else if (next.Match.Length > 0) //TODO: Протестить, если Length == 0, а next - false
                    list.Add(next); 
                
                next = maybeNextItems.Parser.Do(next.Rest);
                while (next.Match.Length > 0)
                {
                    list.Add(next);
                    next = maybeNextItems.Parser.Do(next.Rest);
                }
                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });

            return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = firstItem.Parser.Do(text);
                if (!next.Success)
                    return next;

                var list = new List<LpNode>(0x10);
                if (firstItem.Uncover)
                    list.AddChildrenOrNodeOrNothing(next);
                else if (next.Match.Length > 0)
                    list.Add(next);

                next = maybeNextItems.Parser.Do(next.Rest);
                while (next.Match.Length > 0)
                {
                    list.AddChildrenOrNodeOrNothing(next);
                    next = maybeNextItems.Parser.Do(next.Rest);
                }
                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });
		}




        /// <summary>
        /// Реализует шаблон (first + maybeNext{0,1}).
        /// Очень похожь на комбинатор NextZeroOrMore, но отличается от него только тем, что вместо {0,} стоит {0,1}.
        /// </summary>
        /// <param name="first">Парсер первого элемента.</param>
        /// <param name="maybeNext">Парсер последующих элементов.</param>
        /// <returns>Парсер.</returns>
        [Obsolete("Протестить, добавить юнит-тесты.")]
        public static LpsParser MaybeNext(this LpUncover<LpsParser, LpNode> first, LpUncover<LpsParser, LpNode> maybeNext)
        {
            if (!first.Uncover && !maybeNext.Uncover) return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var nFirst = first.Parser.Do(text);
                if (!nFirst.Success)
                    return nFirst;
                var nNext = maybeNext.Parser.Do(nFirst.Rest);
                if (nNext.Match.Length <= 0)
                    return nFirst;
                return nFirst.Match.Length <= 0 ? nNext : new LpNode(text, nNext.Rest.Index - text.Index, null, nFirst, nNext);
            });


            // maybeNext.Uncover
            if (maybeNext.Uncover) return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = first.Parser.Do(text);
                if (!next.Success)
                    return next;

                var list = new List<LpNode>(0x10);
                if (first.Uncover)
                    list.AddChildrenOrNodeOrNothing(next);
                else if (next.Match.Length > 0)
                    list.Add(next);

                next = maybeNext.Parser.Do(next.Rest);
                if (next.Match.Length > 0)
                    list.AddChildrenOrNodeOrNothing(next);

                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });


            return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = first.Parser.Do(text);
                if (!next.Success)
                    return next;

                var list = new List<LpNode>(0x10);
                if (first.Uncover)
                    list.AddChildrenOrNodeOrNothing(next);
                else if (next.Match.Length > 0)
                    list.Add(next);

                next = maybeNext.Parser.Do(next.Rest);
                if (next.Match.Length > 0)
                    list.Add(next);

                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });
        }

        /// <summary>
        /// Реализует шаблон (first + maybeNext{0,1}).
        /// Очень похожь на комбинатор NextZeroOrMore, но отличается от него только тем, что вместо {0,} стоит {0,1}.
        /// </summary>
        /// <param name="first">Парсер первого элемента.</param>
        /// <param name="maybeNext">Парсер последующих элементов.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser MaybeNext(this LpsChain first, LpUncover<LpsParser, LpNode> maybeNext)
        {
            return MaybeNext((LpUncover<LpsParser, LpNode>)first.ToParser(), maybeNext);
        }

        /// <summary>
        /// Реализует шаблон (first + maybeNext{0,1}).
        /// Очень похожь на комбинатор NextZeroOrMore, но отличается от него только тем, что вместо {0,} стоит {0,1}.
        /// </summary>
        /// <param name="first">Парсер первого элемента.</param>
        /// <param name="maybeNext">Парсер последующих элементов.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser MaybeNext(this LpsParser first, LpUncover<LpsParser, LpNode> maybeNext)
        {
            return MaybeNext((LpUncover<LpsParser, LpNode>)first, maybeNext);
        }

        /// <summary>
        /// Реализует шаблон (first + maybeNext{0,1}).
        /// Очень похожь на комбинатор NextZeroOrMore, но отличается от него только тем, что вместо {0,} стоит {0,1}.
        /// </summary>
        /// <param name="first">Парсер первого элемента.</param>
        /// <param name="maybeNext">Парсер последующих элементов.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser MaybeNext(this LpsParser first, LpsChain maybeNext)
        {
            return MaybeNext((LpUncover<LpsParser, LpNode>)first, maybeNext.ToParser());
        }

		/// <summary>
		/// Функция добавления ноды в список.
		/// Если у ноды есть дети, то добавляет детей вместо ноды. В остальных случаях добавляется нода.
		/// Эта функция используется при включённой опции uncover в некоторых специфических функциях, например MaybeNext.
		/// </summary>
		/// <param name="list">Список.</param>
		/// <param name="node">Нода.</param>
		public static void AddChildrenOrNodeOrNothing(this LinkedList<LpNode> list, LpNode node)
		{
            if (node.Match.Length <= 0)
                return;

			if (node.Children == null)
			{
				list.AddLast(node);
				return;
			}
			var childrens = node.Children.GetEnumerator();
			if (!childrens.MoveNext())
			{
				list.AddLast(node);
				return;
			}
			do
			{
				list.AddLast(childrens.Current);
			}
			while (childrens.MoveNext());
		}

        /// <summary>
        /// Функция добавления ноды в список.
        /// Если у ноды есть дети, то добавляет детей вместо ноды. В остальных случаях добавляется нода.
        /// Эта функция используется при включённой опции uncover в некоторых специфических функциях, например MaybeNext.
        /// </summary>
        /// <param name="list">Список.</param>
        /// <param name="node">Нода.</param>
        public static void AddChildrenOrNodeOrNothing(this IList<LpNode> list, LpNode node)
        {
            if (node.Match.Length <= 0)
                return;
            
            if (node.Children == null)
            {
                list.Add(node);
                return;
            }
            var childrens = node.Children.GetEnumerator();
            if (!childrens.MoveNext())
            {
                list.Add(node);
                return;
            }
            do
            {
                list.Add(childrens.Current);
            }
            while (childrens.MoveNext());
        }


		internal static IEnumerable<LpNode> ZeroOrMore(LpsParser parser, LpText text)
		{
            yield return new LpNode(new LpText(text.Source, text.Index, 0), text);

			var left = parser.Do(text);
			while (left.Success)
			{
				yield return left;

				if (left.Match.Length <= 0 || left.Rest.Length <= 0)
					break;
				
				var right = parser.Do(left.Rest);
				if (!right.Success)
					break;
				left = LpNode.Concat(left, right);
			}
		}

		/// <summary>
		/// Комбинатор. Ноль или более раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <returns>Мультипарсер, возвращающий все варианты соответствий.</returns>
		public static LpmParser ZeroOrMore_(this LpsParser parser)
		{
			return new LpmParser((p) => ZeroOrMore(parser, p));
		}

        /// <summary>
        /// Комбинатор. Ноль или более раз.
        /// </summary>
        /// <param name="predicate">Предикат - функция принадлежности символа заданному множеству.</param>
        /// <returns>Мультипарсер, возвращающий все варианты соответствий.</returns>
        public static LpmParser ZeroOrMore_(this Func<char, bool> predicate)
        {
            return ZeroOrMore_(Lp.One(predicate));
        }


		/// <summary>
		/// Комбинатор. Ноль или более раз.
		/// </summary>
		/// <param name="parser">Парсер.</param>
		/// <param name="text">Текст.</param>
		/// <returns>Все варианты соответствий.</returns>
		internal static IEnumerable<LpNode> ZeroOrMore_(LpmParser parser, LpText text)
		{
			// Zero
            yield return new LpNode(new LpText(text.Source, text.Index, 0), text);

			// OneOrMore
			var results = parser.Do(text);
			while (true)
			{

				bool empty = true;

				// Повторы убирать необходимо обязательно ибо время разбора при неблагоприятных исходах может вырасти экспоненциально.
				results = results.DistinctMatches();
				
				foreach (var oneResult in results)
				{
					if (oneResult.Match.Length <= 0) // Zero уже было.
						continue;

					empty = false;
					yield return oneResult;
				}
				if (empty)
					yield break;

				results = results.NextSelf(parser);
			}
		}

		/// <summary>
		/// Комбинатор. Ноль или более раз.
		/// </summary>
		/// <param name="parser">Мультипарсер.</param>
		/// <returns>Все варианты соответствий.</returns>
		public static LpmParser ZeroOrMore_(this LpmParser parser)
		{
			return new LpmParser((p) => ZeroOrMore_(parser, p).DistinctMatches());
		}

		/// <summary>
		/// Жадный парсер нуля или более символов.
		/// </summary>
		/// <param name="predicate">Предикат для выбора символов.</param>
		/// <returns>Жадный парсер.</returns>
		public static LpsParser ZeroOrMore(this Expression<Func<char, bool>> predicate)
		{
            var func = LpLex.ZeroOrMore(predicate).Compile();
            return new LpsParser(func);

            //return new LpsParser("ZeroOrMore", (text) =>
            //{
            //    int end = text.Length, cur = 0, ind = text.Index;
            //    var str = text.Source;
            //    while (cur < end && predicate(str[ind])) { ++ind; ++cur; }
            //    return LpNode.Take(text, cur);
            //});
		}


        /// <summary>
        /// Конструктор парсера цепочки из ноля или более элементов.
        /// Возвращает парсер, который последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех
        /// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
        /// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
        /// </summary>
        /// <param name="parser">Парсер.</param>
        /// <returns>Парсер.</returns>
        public static LpsParser ZeroOrMore(this LpsChain parser)
        {
            return Lp.ZeroOrMore(new LpCover<LpsParser, LpNode>(parser.ToParser(), false));
        }

        /// <summary>
        /// Конструктор парсера цепочки из ноля или более элементов.
        /// Возвращает парсер, который последовательно применяет parser к тексту, передавая в parser остаток от предыдущего результата, до тех
		/// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
		/// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
		/// </summary>
        /// <param name="parser">Парсер.</param>
		/// <returns>Парсер.</returns>
        public static LpsParser ZeroOrMore(this LpsParser parser)
        {
            return Lp.ZeroOrMore(new LpCover<LpsParser, LpNode>(parser, false));
        }

		/// <summary>
        /// Конструктор парсера цепочки из ноля или более элементов.
		/// Возвращает парсер, который последовательно применяет parserInfo.Parser к тексту, передавая в parserInfo.Parser остаток от предыдущего результата, до тех
		/// пор пока распознаётся текст. Возвращает и объединяет все найденные соответствия в один узел. Между найденными соответствиями не может быть
		/// разрывов. Все найденные соответствия также сохраняются в свойстве Children узла.
		/// </summary>
        /// <param name="parserInfo">Парсер.</param>
		/// <returns>Парсер.</returns>
		public static LpsParser ZeroOrMore(this LpCover<LpsParser, LpNode> parserInfo)
		{
            var parser = parserInfo.Parser;
            if (!parserInfo.Uncover) return new LpsParser(id: null, wrapNode: true, parser: (text) =>
			{
                var next = parser.Do(text);
				if (!next.Success)
					return new LpNode(new LpText(text.Source, text.Index, 0), text);

                // Оказалось, что List в 1.5 раза работает быстрее чем LinkedList, даже на 10-и миллионных массивах.
                // Да и памяти жрёт на одну треть меньше, если LpNode - класс, а не структура.
                var list = new List<LpNode>(0x10);
				while (next.Match.Length > 0)
				{
					list.Add(next);
					next = parser.Do(next.Rest);
				}
				if (list.Count <= 1)
					return list.Count == 0 ? next : list[0];
				return new LpNode(text, next.Rest.Index - text.Index, null, list);
			});

            return new LpsParser(id: null, wrapNode: true, parser: (text) =>
            {
                var next = parser.Do(text);
                if (!next.Success)
                    return new LpNode(new LpText(text.Source, text.Index, 0), text);

                var list = new List<LpNode>(0x10);
                while (next.Match.Length > 0)
                {
                    list.AddChildrenOrNodeOrNothing(next);
                    next = parser.Do(next.Rest);
                }
                if (list.Count <= 1)
                    return list.Count == 0 ? next : list[0];
                return new LpNode(text, next.Rest.Index - text.Index, null, list);
            });
		}

		/// <summary>
		/// Жадный парсер нуля или более символов.
		/// </summary>
		/// <param name="ch">Символ.</param>
		/// <returns>Жадный парсер.</returns>
		public static LpsParser ZeroOrMore(char ch)
		{
			return new LpsParser((text) =>
			{
				int end = text.Length, cur = 0, ind = text.Index;
				var str = text.Source;
				while (cur < end && str[ind] == ch) { ++ind; ++cur; }
                return new LpNode(text, cur); 
			});
		}

		#endregion ZeroOrMore

    }
}
